package com.company.algo.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/find-eventual-safe-states/
 前面的解法会超时，所以需要加上记忆化
 每个点可能的状态: 白色0:点是未走过的, 灰色1:点是走过的不确定安不安全，黑色2:点是安全的
 每次遍历的点都可以记录该点的状态，这样可以达到剪枝的效果

 当我们首次访问一个节点时，将其标记为灰色，并继续搜索与其相连的节点。
 如果在搜索过程中遇到了一个灰色节点，则说明找到了一个环，此时退出搜索，栈中的节点仍保持为灰色，这一做法可以将「找到了环」这一信息传递到栈中的所有节点上。
 如果搜索过程中没有遇到灰色节点，则说明没有遇到环，那么递归返回前，我们将其标记由灰色改为黑色，即表示它是一个安全的节点。

 */
public class find_eventual_safe_states2 {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        List<Integer> ans = new ArrayList<Integer>();
        for (int i = 0; i < n; ++i) {
            if (safe(graph, color, i)) {
                ans.add(i);
            }
        }
        return ans;
    }

    public boolean safe(int[][] graph, int[] color, int x) {
        if (color[x] > 0) {
            return color[x] == 2;
        }
        color[x] = 1;
        for (int n : graph[x]) {
            if (!safe(graph, color, n)) {
                return false;
            }
        }
        color[x] = 2;
        return true;
    }


    public static void main(String[] args) {
        int[][] graph = new int[5][];
        graph[0] = new int[]{};
        graph[1] = new int[]{0,2,3,4};
        graph[2] = new int[]{3};
        graph[3] = new int[]{4};
        graph[4] = new int[]{};
//        graph[5] = new int[]{};
//        graph[6] = new int[]{};
        find_eventual_safe_states2 Main = new find_eventual_safe_states2();
        System.out.println(Main.eventualSafeNodes(graph));
    }
}
